package com.lihepeng.leecode.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
 * <p>
 * 例如，从根到叶子节点路径 1->2->3 代表数字 123。
 * <p>
 * 计算从根到叶子节点生成的所有数字之和。
 * <p>
 * 说明: 叶子节点是指没有子节点的节点。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [1,2,3]
 * 1
 * / \
 * 2   3
 * 输出: 25
 * 解释:
 * 从根到叶子节点路径 1->2 代表数字 12.
 * 从根到叶子节点路径 1->3 代表数字 13.
 * 因此，数字总和 = 12 + 13 = 25.
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sum-root-to-leaf-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution129 {
    // 深度优先遍历
    public int sumNumbers(TreeNode root) {

        return dfs(root, 0);

    }

    /**
     * @param root
     * @param preSum
     * @return
     */
    public int dfs(TreeNode root, int preSum) {
        if (root == null) {
            return 0;
        }
        int sum = preSum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return sum;
        } else {
            return dfs(root.left, sum) + dfs(root.right, sum);
        }

    }

    /**
     * 广度优先遍历
     *
     * @param root
     * @return
     */

    public int sumNumbers01(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int sum = 0;
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> numQueue = new LinkedList<>();
        nodeQueue.offer(root);
        numQueue.offer(root.val);
        while (!nodeQueue.isEmpty()) {
            TreeNode treeNode = nodeQueue.poll();
            int num = numQueue.poll();
            TreeNode leftNode = treeNode.left, rightNode = treeNode.right;
            if (leftNode == null && rightNode == null) {
                sum += num;
            } else {
                if (leftNode != null) {
                    nodeQueue.offer(leftNode);
                    numQueue.offer(num * 10 + leftNode.val);
                } else {
                    nodeQueue.offer(rightNode);
                    numQueue.offer(num * 10 + rightNode.val);
                }
            }
        }
        return sum;
    }

}
